#ifndef __HASHMAP_H__
#define __HASHMAP_H__

/*
===============================================================================

HashMap<Type> -- key: Str, value: Type
General hash table. Slower than HashIndex but it can also be used for
linked lists and other data structures than just indexes or arrays.

===============================================================================
*/

namespace inf {

    template< typename Type >
    class HashMap {
    public:
                        HashMap( void );
                        HashMap( const HashMap<Type> &map );
                        ~HashMap( void );

        void			clear( void );
        void			delete_contents( bool clear = true );    // only called, when Type is a pointer type.
        void			swap( HashMap& rhs );
        
        size_t			total_size( void ) const;         // returns total size of allocated memory including size of hash table type
        size_t			allocated( void ) const;    // returns total size of allocated memory

        // returns number in the range [0-100] representing the spread over the hash table
        int				get_spread( void ) const;

        Type &			set( const char *key, const Type &value );
        bool			get( const char *key, Type **value = NULL );
        bool			get( const char *key, const Type **value = NULL ) const;

        // the entire contents can be iterated over, but note that the
        // exact index for a given element may change when new elements are added
        int				size( void ) const;
        const Str	&	get_key( int index ) const;
        Type *			get_index( int index );
        const Type *	get_index( int index ) const;
        bool			remove( const char *key );

        const List<Str>&    get_key_list( void ) const { return keyList; }
        const List<Type>&   get_value_list( void ) const { return list; }
    private:
        List<Type>	list;
        HashIndex	    hashIndex;
        List<Str>	keyList;
    };

    template< typename Type >
    HashMap<Type>::HashMap( void ) {
    }

    template< typename Type >
    HashMap<Type>::HashMap( const HashMap<Type> &map ) {
        list = map.list;
        hashIndex = map.hashIndex;
        keyList = map.keyList;
    }

    template< typename Type >
    HashMap<Type>::~HashMap( void ) {
        clear();
    }

    template< typename Type >
    void HashMap<Type>::clear( void ) {
        list.clear();
        hashIndex.clear();
        keyList.clear();
    }

    template< typename Type >
    void HashMap<Type>::delete_contents( bool clear ) {
        inf::delete_contents( list, clear );
        if ( clear ) {
            // list already cleared
            hashIndex.clear();
            keyList.clear();
        }
    }

    template< typename Type >
    void HashMap<Type>::swap( HashMap& rhs ) {
        hashIndex.swap( rhs.hashIndex );
        list.swap( rhs.list );
        keyList.swap( rhs.keyList );
    }


    template< typename Type >
    size_t HashMap<Type>::total_size( void ) const {
        return list.total_size() + hashIndex.total_size() + keyList.total_size();
    }

    template< typename Type >
    size_t HashMap<Type>::allocated( void ) const {
        return list.allocated();
    }

    template< typename Type >
    int HashMap<Type>::get_spread( void ) const {
        return hashIndex.get_spread();
    }

    /*
    ================
    Sets a key in the table to be a certain value, adds it if it's not already there
    Returns a reference to the value in the table
    ================
    */
    template< typename Type >
    Type &HashMap<Type>::set( const char *key, const Type& value ) {
        Type *existingValue;
        if ( get( key, &existingValue ) ) {
            *existingValue = value;
            return *existingValue;
        } else {
            int index = list.append( value );
            keyList.append( key );
            hashIndex.add( hashIndex.generate_key( key ), index );
            return list[index];
        }
    }

    template< typename Type >
    bool HashMap<Type>::get( const char *key, Type **value ) {
        int hashKey = hashIndex.generate_key( key );
        int i;
        for ( i = hashIndex.get_first( hashKey ); i != HashIndex::NULL_INDEX; i = hashIndex.get_next( i ) ) {
            if ( keyList[i].cmp( key ) == 0 ) {
                if ( value ) {
                    *value = &list[ i ];
                }
                return true;
            }
        }
        if ( value ) {
            *value = NULL;
        }
        return false;
    }

    template< typename Type >
    bool HashMap<Type>::get( const char *key, const Type **value ) const {
        return const_cast<HashMap<Type> *>(this)->get( key, const_cast<Type **>( value ) );
    }

    template< typename Type >
    int HashMap<Type>::size( void ) const {
        return list.size();
    }

    /*
    ================
    the entire contents can be itterated over, but note that the
    exact index for a given element may change when new elements are added
    ================
    */
    template< typename Type >
    const Str &HashMap<Type>::get_key( int index ) const {
        if ( index >= 0 && index < list.size() ) {
            return keyList[index];
        }
        static Str blank;
        return blank;
    }

    /*
    ================
    the entire contents can be itterated over, but note that the
    exact index for a given element may change when new elements are added
    ================
    */
    template< typename Type >
    Type *HashMap<Type>::get_index( int index ) {
        if ( index >= 0 && index < list.size() ) {
            return &list[index];
        }
        return NULL;
    }

    /*
    ================
    the entire contents can be itterated over, but note that the
    exact index for a given element may change when new elements are added
    ================
    */
    template< typename Type >
    const Type *HashMap<Type>::get_index( int index ) const {
        if ( index >= 0 && index < list.size() ) {
            return &list[index];
        }
        return NULL;
    }

    template< typename Type >
    bool HashMap<Type>::remove( const char *key ) {
        int hashKey = hashIndex.generate_key( key );	
        int i;
        for ( i = hashIndex.get_first( hashKey ); i != HashIndex::NULL_INDEX; i = hashIndex.get_next( i ) ) {
            if ( keyList[ i ].cmp( key ) == 0 ) {
                hashIndex.remove_index( hashKey, i );
                keyList.remove_index( i );
                list.remove_index( i );
                return true;
            }
        }
        return false;
    }

}   // ::inf

#endif /* !__HASHMAP_H__ */
